/**
 * 62. 不同路径
 * https://leetcode-cn.com/problems/unique-paths/
 */

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
function uniquePaths(m, n) {
  const grid = new Array(n);
  for (let i = 0; i < n; i += 1) {
    grid[i] = new Array(m).fill(0);
  }
  for (let j = 0; j < m; j += 1) {
    grid[0][j] = 1;
  }
  for (let i = 1; i < n; i += 1) {
    grid[i][0] = 1;
  }
  for (let i = 1; i < n; i += 1) {
    for (let j = 1; j < m; j += 1) {
      grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
    }
  }
  return grid[n - 1][m - 1];
}

console.log(uniquePaths(3, 7) === 28);
console.log(uniquePaths(3, 2) === 3);
console.log(uniquePaths(7, 3) === 28);
console.log(uniquePaths(3, 3) === 6);
console.log(uniquePaths(1, 1) === 1);
